# 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

def TreeDepth(self, pRoot):
    # 层次遍历二叉树
    def helper(node, level):
        if not node:
            return
        else:
            sol[level - 1].append(node)
            if len(sol) == level:  # 遍历到新层时，只有最左边的结点使得等式成立
                sol.append([])
            helper(node.left, level + 1)
            helper(node.right, level + 1)
    sol = [[]]
    helper(pRoot,1)
    return len(sol)-1#因为最后肯定多加了一个空的，所以要减一

# 解法2：改进的递归
def TreeDepth(self, pRoot):
    # write code here
    # 使用层次遍历
    # 当树为空直接返回0
    if pRoot is None:
        return 0
    # 如果该树只有一个结点，它的深度为1.如果根节点只有左子树没有右子树，
    # 那么树的深度为左子树的深度加1；同样，如果只有右子树没有左子树，
    # 那么树的深度为右子树的深度加1。如果既有左子树也有右子树，
    # 那该树的深度就是左子树和右子树的最大值加1.
    count = max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
    return count